1. Field of the Invention
The present invention relates generally to improvements in decoding encoded data. More particularly, the present invention relates to improvements in decoding data which has been encoded using rate-k/n convolutional codes or other high rate trellis codes.
2. Description of Prior Art
In many data processing applications, it is often desirable to encode a data stream using trellis codes or other data encoding techniques. For example, in digital communication systems, trellis coding of modulation data, when combined with an appropriate mapping of the encoded data to a transmitted signal set, can improve the signal-to-noise ratio of a received signal without an increase in transmitted signal power or bandwidth. See G. Ungerboeck "Channel Coding with Multilevel/Phase Signals," IEEE Transactions on Information Theory, Vol. IT-28, pp. 55-67, January 1982, which is incorporated by reference herein. The signal-to-noise improvement attributable to data encoding is referred to as coding gain, and results in increased bandwidth efficiency. The above-cited Ungerboeck article demonstrates that rate n/(n+1) trellis codes which are mapped into a 2.sup.n+1 -point signal set can provide significant coding gain when compared to uncoded 2.sup.n -point signal sets. The amount of coding gain achieved in a given application depends upon a number of factors, including the code rate and the number of states in the code. In general, the code rate is a function of the number of uncoded data bits used to generate each sequence of code bits, while the number of states in the code may be a function of, for example, the number of storage elements in the encoder memory.
Rate-k/n convolutional codes are one type of high rate trellis code. In rate-k/n convolutional codes, a group of k uncoded data bits, also called a data symbol, is encoded using n code bits, collectively referred to as a code symbol. Rate-k/n encoders include an encoder memory which operates as a shift register. Trellis codes are a more general class of codes in which state transitions may be diagrammed in the form of a trellis, but which do not necessarily exhibit shift register-like characteristics. Low rate codes include rate-1/n convolutional codes, in which each one-bit data symbol is encoded using an n-bit code symbol. For both high and low rate codes, the encoded data is often decoded using hardware which implements the well-known Viterbi maximum-likelihood algorithm described in, for example, G. D. Forney, Jr., "The Viterbi Algorithm," Proceedings of the IEEE, pp. 268-278, March 1973, which is incorporated by reference herein. The Viterbi algorithm is a recursive solution to the problem of estimating the state sequence of a finite-state Markov process. In a Markov process, such as the process of encoding data using convolutional codes, the probability of being in a given state x.sub.t+1 at time t+1 depends only on the state x.sub.t at time t, referred to herein as the predecessor state. The Viterbi algorithm provides optimal decoding in the sense that, for a given set of encoded data, it finds the maximum-likelihood path through a trellis of possible state transitions.
A number of area-efficient decoder designs, which attempt to minimize the circuit area required to implement the Viterbi decoding algorithm at a given processing speed, have been developed for low rate codes. See, for example, P. G. Gulak and T. Kailath, "Locally Connected VLSI Architectures for the Viterbi Algorithm," IEEE Journal on Selected Areas in Communications, Vol. 6, No. 3, pp. 527-537, April 1988, and H-D. Lin et al., "Folded Viterbi Decoders for Convolutional Codes," IEEE VLSI Signal Processing, Vol. IV, IEEE Press, 1990, both of which are incorporated by reference herein. High rate codes, however, generally require a substantially more complex set of hardware in order to provide maximum coding gain using, for example, the Viterbi algorithm. As a result, currently available decoders for rate-k/n convolutional codes and other high rate trellis codes typically utilize suboptimal decoding in order to reduce decoder complexity and cost. Exemplary suboptimal decoding algorithms are described in, for example, pp. 382-388 of R. E. Blahut, "Theory and Practice of Error Control Codes," Addison-Wesley, Reading, Mass., 1984, which are incorporated by reference herein. Unfortunately, reductions in decoder hardware complexity from the use of a suboptimal decoding algorithm usually come at the expense of coding gain.
One reason for the excessive hardware complexity is that optimal high rate Viterbi decoders typically utilize processing elements in which path metrics, measuring the likelihood of possible sequences of predecessor states, are accessed and updated in parallel. The updated path metrics are then compared to select the most likely state sequence corresponding to a given set of encoded data. In general, each processing element in a rate-kln decoder will require 2.sup.k parallel metric inputs. In addition, because the total number of decoder processing elements generally increases as a function of the desired coding gain, decoders for high rate codes often include significantly larger numbers of processing elements. As a result, the rate-k/n decoder will typically include more interconnections and occupy a much larger circuit area than a rate-1/n decoder. Area-efficient techniques developed for low rate codes, however, generally do not alleviate the increased circuit area problem which accompanies use of larger numbers of parallel-input processing elements. Under current practice, therefore, it is difficult to achieve the advantages of high rate codes in a cost-effective manner.
As is apparent from the above, a need exists for improved area-efficient decoders for high rate trellis codes. The improved decoders should exhibit reduced hardware complexity without resorting to suboptimal decoding algorithms.